package style.Leetcode.初级算法.array.array_20221015_1_长度最小的子数组;

/**
 * 209. 长度最小的子数组
 *
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，
 * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *
 * 示例 1：
 * 输入：target = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组[4,3]是该条件下的长度最小的子数组。
 * 示例 2：
 * 输入：target = 4, nums = [1,4,4]
 * 输出：1
 * 示例 3：
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 * 输出：0
 *
 */
public class Solution {

    /**
     * 思路：滑动窗口
     *      先找到第一个趋近于 target 的窗口 （小于等于 target 但是再加上一个数就大于 target）
     *      sum 先 减掉左侧一个数，右侧继续往前走，碰到趋近点就继续重复操作
     */
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        if (length == 0) return 0;
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < length) {
            sum += nums[end];
            while (sum >= target) {
                ans = Math.min(ans, end - start +1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minSubArrayLen(13, new int[]{2,3,4,3,6,6}));
    }
}
